∂06-SEP-74  1659		P,PAW
 To: Fields @ISI
 Subject:  Stanford A.P. Bullets
 
 1.  Automatic Coding:  Choice of Data Structures
 
 A system has  been developed which,  given an algorithm  expressed in
 terms  of  high-level information  structures such  as  sets, ordered
 sets, and relations, automatically chooses efficient  representations
 and  produces   a  new  program  that   uses  these  representations.
 Representations  are picked  from a  fixed library of  low-level data
 structures including linked-lists, binary trees and hash tables.  The
 representations  are chosen by  attempting to minimize  the predicted
 space-time integral of  the user's program  execution.   [Predictions
 are  based upon  statistics  of  information structure  use  provided
 directly  by the user and  collected by monitoring  executions of the
 user  program  using  default  representations  for  the   high-level
 structures.] This  is a  practical system  and could  be incorporated
 into  SAIL or another high-level language  programming system.  [work
 performed by Jim Low]
 
 2.  Advances in Program Construction using Formal Methods
 
 Completed an advanced (although still experimental) formal system for
 automatic  programming.  In  this paradigm  one begins with  a formal
 statement of the requirements  that a program  must satisfy and  then
 the  system   syntehsizes  a   correct  program   that  meets   these
 requirements.     A  combination  of  automatic  theorem-proving  and
 problem-solving techniques is  used to synthesize  the program.   The
 programs constructed  are expressed in  a subset of  ALGOL containing
 assignments, function calls, conditional statements, WHILE loops, and
 non-recursive procedure calls.  The system has been  used to generate
 programs  for   symbolic  manipulation,  robot   control,  every  day
 planning,  and  computing  arithmetical  functions.    The   programs
 generated can be several pages long.  This system represents advances
 in the formalism  for expressing programs, in problem solving methods
 specific to  automatic  programming,  and  in  program-writing  power
 [length of programs produced].  [work by Luckham and Buchanan]
 
 3.  Inferring LISP Programs from Examples
 
 Completed a program  that infers recursive  list-processing functions
 from   input-output   pairs.     For  example,   given   the  example
 specification
 
 	(A B C D) → (D D C C B B A A)
          input        output
 
 the  system produces  a "reverse-and-double"  program.   This  system
 shows   the   feasibility  of   more  natural   methods   of  program
 specification, but  the  work  is  still experimental  and  there  is
 considerable  room  for  progress.  [work done  by  Green,  Shaw  and
 Swartout]
 
 
 4.  Craig, I can rewrite these if you want.  You might want to delete
 the bracketed portions.
 
 					Cordell
 
 cc:  J. McCarthy, L. Earnest